In the field of computer-aided design, it is known to use a digital computer having a program stored therein for routing interconnections between one module and another module on a planar field. In addition, it is also known to use a digital computer having a program stored therein for compacting the position of the modules after they are interconnected or routed. Typically, the modules are semiconductor integrated circuits and the interconnections are electrical wires. An example of a prior art technique to perform the routing of interconnections between modules and/or the positioning of modules after they have been routed, by the use of a digital computer having a program stored therein, is disclosed in U.S. Pat. No. 3,681,782. That reference teaches a machine process for positioning interconnected components to minimize interconnecting line length. See also "Gridless Channel Routing and Compaction for Cell Based Custom IC Layout" by Harold Rabbie and Jacob Jacobsson, IEEE 1986 Custom Integrated Circuits Conference, page 297, published on May 12, 1986. In addition, see "A New Gridless Channel Router: Yet Another Channel Router II (YACR-II)" by A. Sangiovanni-Vincentelli, M. Santomauro and Jim Reid, PROC. International Conference On Computer-Aided Design 84, pages 72-75, 1984; and "An Industrial World Channel Router For Non-Rectangular Channels" by C. H. Ng, PRO. 23rd Third Design Automation Conference, pages 490-494, 1986 (hereinafter the latter two references are referred collectively as: "YACR").
Of all the known prior art relating to a machine process for routing interconnections between two modules, the most relevant reference of which the applicant is aware is the YACR reference. The invention set forth herein is an improvement to the basic YACR method.
Of all the known prior art relating to a machine process for positioning the modules on a planar field by the use of a programmed digital computer, the most relevant reference of which the applicant is aware is the article by Rabbi and Jacobsson. In Rabbi and Jacobsson, compaction is done by moving tracks against a contour in one direction only. However, applicant believes that he had conceived of the invention prior to the publication date of the Rabbi and Jacobsson reference, and had worked diligently to reduce the invention, which occurred after the publication date. The present invention is also an improvement to that method.